// [279]-完全平方数
struct Solution;

//leetcode submit region begin(Prohibit modification and deletion)
impl Solution {
    pub fn num_squares(n: i32) -> i32 {
        let mut dp = [i32::MAX; 10001];
        dp[0] = 0;
        for i in 1..=100 {
            for j in i * i..=10000 {
                dp[j] = dp[j].min(dp[j-i*i] + 1)
            }
        }
        dp[n as usize]
    }
}
//leetcode submit region end(Prohibit modification and deletion)

/// 总结：给定某个数，求符合规则的数量 => 动态规划

#[test]
fn main() {
    assert_eq!(Solution::num_squares(12), 3);
    assert_eq!(Solution::num_squares(13), 2);
}
